{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #二叉树染色"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #dynamic-programming #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #动态规划 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxValue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树染色"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "小扣有一个根结点为 `root` 的二叉树模型，初始所有结点均为白色，可以用蓝色染料给模型结点染色，模型的每个结点有一个 `val` 价值。小扣出于美观考虑，希望最后二叉树上每个蓝色相连部分的结点个数不能超过 `k` 个，求所有染成蓝色的结点价值总和最大是多少？\n",
    "\n",
    "\n",
    "**示例 1：**\n",
    "> 输入：`root = [5,2,3,4], k = 2`\n",
    ">\n",
    "> 输出：`12`\n",
    ">\n",
    "> 解释：`结点 5、3、4 染成蓝色，获得最大的价值 5+3+4=12`\n",
    "![image.png](https://pic.leetcode-cn.com/1616126267-BqaCRj-image.png)\n",
    "\n",
    "\n",
    "**示例 2：**\n",
    "> 输入：`root = [4,1,3,9,null,null,2], k = 2`\n",
    ">\n",
    "> 输出：`16`\n",
    ">\n",
    "> 解释：结点 4、3、9 染成蓝色，获得最大的价值 4+3+9=16\n",
    "![image.png](https://pic.leetcode-cn.com/1616126301-gJbhba-image.png)\n",
    "\n",
    "\n",
    "\n",
    "**提示：**\n",
    "+ `1 <= k <= 10`\n",
    "+ `1 <= val <= 10000`\n",
    "+ `1 <= 结点数量 <= 10000`\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [er-cha-shu-ran-se-UGC](https://leetcode.cn/problems/er-cha-shu-ran-se-UGC/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [er-cha-shu-ran-se-UGC](https://leetcode.cn/problems/er-cha-shu-ran-se-UGC/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,2,3,4]\\n2', '[4,1,3,9,null,null,2]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        def helper(root):\n",
    "            if not root:\n",
    "                return [0] * (k+1)\n",
    "            r_list = helper(root.right)\n",
    "            l_list = helper(root.left)\n",
    "\n",
    "            res = [0] * (k+1)\n",
    "            res[0] = max(r_list) + max(l_list)\n",
    "            res[1] = root.val+r_list[0]+l_list[0]\n",
    "\n",
    "            for i in range(2,k+1):\n",
    "                for j in range(0,i):\n",
    "                    if r_list[j] + l_list[i-1-j] + root.val > res[i]:\n",
    "                        res[i] = r_list[j] + l_list[i-1-j] + root.val\n",
    "\n",
    "            return res\n",
    "        return max(helper(root))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "\n",
    "        def dfs(node):\n",
    "\n",
    "            if not node:\n",
    "                return [0] * (k+1)\n",
    "\n",
    "            lDP = dfs(node.left)\n",
    "            rDP = dfs(node.right)\n",
    "\n",
    "            dp = [0] * (k+1)\n",
    "\n",
    "            # 选择node时\n",
    "            dp[0] = max(lDP) + max(rDP)\n",
    "\n",
    "            for i in range(1, k+1):\n",
    "                for j in range(i):\n",
    "\\\n",
    "                    dp[i] = max(dp[i], lDP[j] + rDP[i - 1 - j] + node.val)\n",
    "\n",
    "            return dp\n",
    "        \n",
    "        ret = dfs(root)\n",
    "\n",
    "        return max(ret)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        return max(self.search(root, k))\n",
    "    \n",
    "    def search(self, node: TreeNode, k:int) -> List[int]:\n",
    "        if node.left == None and node.right == None:\n",
    "            dp = [0, node.val] # dp[0] 代表当前node不染色，dp[n]代表当前node染色且有n个连续染色节点\n",
    "            # print(f'current: {node.val}, dp: {dp}')\n",
    "            \n",
    "            return dp\n",
    "        elif node.left == None:\n",
    "            dp = self.search(node.right, k)\n",
    "            max_dp = max(dp)\n",
    "            dp = [x+node.val for x in dp]\n",
    "            dp.insert(0, max_dp)\n",
    "            dp = dp[:k+1]\n",
    "            # print(f'current: {node.val}, dp: {dp}')\n",
    "            \n",
    "            return dp\n",
    "        elif node.right == None:\n",
    "            dp = self.search(node.left, k)\n",
    "            max_dp = max(dp)\n",
    "            dp = [x+node.val for x in dp]\n",
    "            dp.insert(0, max_dp)\n",
    "            dp = dp[:k+1]\n",
    "            # print(f'current: {node.val}, dp: {dp}')\n",
    "            \n",
    "            return dp\n",
    "        else:\n",
    "            dp_left = self.search(node.left, k)\n",
    "            dp_right = self.search(node.right, k)\n",
    "            new_dp = [0 for _ in range(len(dp_left) + len(dp_right) + 1)]\n",
    "\n",
    "            for i in range(len(dp_left)):\n",
    "                for j in range(len(dp_right)):\n",
    "                    if (dp_left[i] + dp_right[j]) > new_dp[0] and i <= k and j <= k:\n",
    "                        new_dp[0] = dp_left[i] + dp_right[j]\n",
    "                    if dp_left[i] + dp_right[j] + node.val > new_dp[i+j+1] and i + j + 1 <= k:\n",
    "                        new_dp[i+j+1] = dp_left[i] + dp_right[j] + node.val\n",
    "            \n",
    "            # print(f'current: {node.val}, new_dp: {new_dp}')\n",
    "            return new_dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return [0] * (k + 1)\n",
    "            \n",
    "            dr = dfs(node.right)\n",
    "            dl = dfs(node.left)\n",
    "\n",
    "            dp = [0] * (k + 1)\n",
    "            dp[0] = max(dr) + max(dl)\n",
    "\n",
    "            for i in range(1, k+1):\n",
    "                dp[i] = max((dl[j] + dr[i-1-j] for j in range(i)), default=0) + node.val\n",
    "            return dp\n",
    "        \n",
    "        return max(dfs(root))\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "\n",
    "        def traversal(root):\n",
    "\n",
    "            if not root:\n",
    "                return [0] * (k+1)\n",
    "\n",
    "            dl = traversal(root.left)\n",
    "            dr = traversal(root.right)\n",
    "            dp = [0] * (k+1)\n",
    "            dp[0] = max(dl) + max(dr)\n",
    "            for i in range(1,k+1):\n",
    "                for j in range(i):\n",
    "                    dp[i] = max(dl[j] + dr[i-1-j] + root.val, dp[i])\n",
    "            return dp\n",
    "\n",
    "        dp = traversal(root)\n",
    "\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return [0]*(k+1)\n",
    "            \n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "            res = [0]*(k+1)\n",
    "            res[0] = max(left)+max(right)\n",
    "            for i in range(1,k+1):\n",
    "                for j in range(i):\n",
    "                    res[i] = max(res[i],root.val+left[j]+right[i-j-1])\n",
    "            return res\n",
    "        \n",
    "        return max(dfs(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return [0] * (k + 1)\n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "            dp = [0] * (k + 1)\n",
    "            #当前节点染色\n",
    "            #枚举以当前节点为根的子树的大小\n",
    "            for i in range(1, k + 1):\n",
    "                #枚举左子树的大小\n",
    "                for j in range(i):\n",
    "                    dp[i] = max(dp[i], left[j] + right[i - j - 1] + root.val)\n",
    "            #当前节点不染色\n",
    "            dp[0] = max(left) + max(right)\n",
    "            return dp\n",
    "        return max(dfs(root))\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return [0 for _ in range(k+1)]\n",
    "\n",
    "            zhuangl = dfs(root.left)\n",
    "            zhuangr = dfs(root.right)\n",
    "\n",
    "            new = [0 for _ in range(k+1)]\n",
    "            new[0] = max(zhuangl)+max(zhuangr)\n",
    "            for i in range(1,k+1):\n",
    "                maxx = -1\n",
    "                for j in range(i):\n",
    "                    maxx = max(maxx,zhuangl[j]+zhuangr[i-j-1])\n",
    "\n",
    "                new[i] = maxx + root.val \n",
    "            print(new)\n",
    "            return new \n",
    "        return max(dfs(root))\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        \n",
    "        # dfs, return a dict of key as blue height from node and value of max sum\n",
    "        # and lager key must have a bigger max sum\n",
    "        def dfs(n):\n",
    "            if not n:\n",
    "                return {0: 0}\n",
    "\n",
    "            ld = dfs(n.left)\n",
    "            rd = dfs(n.right)\n",
    "\n",
    "            # print(f'n: {n}, ld: {ld}, rd: {rd}')\n",
    "\n",
    "            ret = defaultdict(int)\n",
    "            for kl, sl in ld.items():\n",
    "                for kr, sr in rd.items():\n",
    "                    ret[0] = max(ret[0], sl + sr)\n",
    "                    \n",
    "                    if kl + kr + 1 <= k:\n",
    "                        cur_k = kl + kr + 1\n",
    "                        ret[cur_k] = max(ret[cur_k], sl + sr + n.val)\n",
    "            \n",
    "            return ret\n",
    "        \n",
    "        return max(dfs(root).values())\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        def dfs(root):\n",
    "            ans = [0] * (k + 1)\n",
    "            if root is None:\n",
    "                return ans\n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "            ans[0] = max(left) + max(right)\n",
    "            for i in range(k):\n",
    "                for j in range(k-i):\n",
    "                    ans[i+j+1] = max(ans[i+j+1],left[i] + right[j] + root.val)\n",
    "            return ans\n",
    "        return max(dfs(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "\n",
    "        def dfs(root):\n",
    "            # 空节点价值全为0\n",
    "            res = [0]*(k+1)\n",
    "            if not root:\n",
    "                return res\n",
    "            \n",
    "            # 递归获取左右节点的状态\n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "            # 按照转移公式进行计算\n",
    "            res[0] = max(left) + max(right)\n",
    "            for i in range(k):\n",
    "                for j in range(k-i):\n",
    "                    if left[i]+right[j]+root.val > res[i+j+1]:\n",
    "                        res[i+j+1] = left[i]+right[j]+root.val\n",
    "            return res\n",
    "\n",
    "        return max(dfs(root))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        def dfs(root, k):\n",
    "            f = [0] * (k + 1)\n",
    "            if not root:\n",
    "                return f\n",
    "            left_f = dfs(root.left, k)\n",
    "            right_f = dfs(root.right, k)\n",
    "            f[0] = max(left_f) + max(right_f)\n",
    "            for i in range(1, k+1):\n",
    "                for j in range(i):\n",
    "                    f[i] = max(f[i], root.val + left_f[j] + right_f[i-j-1])\n",
    "            return f\n",
    "        res = dfs(root, k)\n",
    "        return max(res)\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        def dfs(node: TreeNode) -> List[int]:\n",
    "            res = [-inf] * (k + 1)\n",
    "            res[0] = 0\n",
    "            if not node:\n",
    "                return res\n",
    "            dpl = dfs(node.left)\n",
    "            dpr = dfs(node.right)\n",
    "            res[0] = max(dpl) + max(dpr)\n",
    "            for s in range(1, k+1):\n",
    "                for l in range(0, s):\n",
    "                    r = s - l - 1\n",
    "                    res[s] = max(res[s], dpl[l] + dpr[r])\n",
    "                res[s] += node.val\n",
    "            return res\n",
    "\n",
    "        return max(dfs(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "\n",
    "        # @cache\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return [0] + [-inf] * k \n",
    "            res = [-inf] * (k + 1)\n",
    "            l, r = dfs(node.left), dfs(node.right)\n",
    "            res[0] = max(l) + max(r)\n",
    "            for i, j in enumerate(l):\n",
    "                for l, m in enumerate(r):\n",
    "                    if i + l + 1 > k:\n",
    "                        break                     \n",
    "                    res[i + l + 1] = max(res[i + l + 1], j + m + node.val)\n",
    "            return res \n",
    "        \n",
    "        ans = max(dfs(root))\n",
    "        # dfs.cache_clear()\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "\n",
    "        def dfs(root):\n",
    "            f=[0]*(k+1)\n",
    "            if not root:\n",
    "                return f\n",
    "            left=dfs(root.left)\n",
    "            right=dfs(root.right)\n",
    "\n",
    "            f[0]=max(left)+max(right) #当前节点不染色\n",
    "\n",
    "            for i in range(1,k+1):\n",
    "                f[i]=max(left[j]+right[i-j-1] for j in range(i))+root.val\n",
    "            \n",
    "            return f\n",
    "        \n",
    "        return max(dfs(root))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        def dfs(tree) -> list[int]:\n",
    "            dp = [0]*(k+1)\n",
    "            if not tree:\n",
    "                return dp\n",
    "            left = dfs(tree.left)\n",
    "            right = dfs(tree.right)\n",
    "            dp[0] = left[-1] + right[-1]\n",
    "            for i in range(1,k+1):\n",
    "                dp[i] = max(dp[i-1], tree.val + max(left[j] + right[i-1-j] for j in range(i)))\n",
    "            return dp\n",
    "        return dfs(root)[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        def dfs(node):\n",
    "            dp=[0]*(k+1)\n",
    "            if not node:\n",
    "                return dp\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            dp[0] = max(left)+max(right)\n",
    "            for i in range(1,k+1):\n",
    "                dp[i] = max(left[l]+right[i-1-l]+node.val for l in range(i))\n",
    "            return dp\n",
    "        return max(dfs(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return [0] + [-inf] * k \n",
    "            res = [-inf] * (k + 1)\n",
    "            l, r = dfs(node.left), dfs(node.right)\n",
    "            res[0] = max(l) + max(r)\n",
    "            for i, j in enumerate(l):\n",
    "                for l, m in enumerate(r):\n",
    "                    if i + l + 1 > k:\n",
    "                        break                     \n",
    "                    res[i + l + 1] = max(res[i + l + 1], j + m + node.val)\n",
    "            return res \n",
    "        \n",
    "        ans = max(dfs(root))\n",
    "        dfs.cache_clear()\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        def f(node):\n",
    "            if not node: return [0]*(k+1)\n",
    "            if not node.left and not node.right: return [0] + [node.val] * k\n",
    "            l,r = map(f,[node.left,node.right])\n",
    "            res = [l[k]+r[k]] + [max(l[j]+r[i-j-1]+node.val for j in range(i)) for i in range(1,k+1)]\n",
    "            for i in range(k): res[i+1] = max(res[i],res[i+1])\n",
    "            return res\n",
    "        return f(root)[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def dfs (self , u , num , k , dp):\n",
    "        dp[num] = [-10**9] * 11\n",
    "        dp[num][0] = 0\n",
    "        dp[num][1] = u.val \n",
    "        if u.left != None:\n",
    "            self.dfs(u.left , num * 2 , k , dp)\n",
    "            dp[num][0] += max(dp[num * 2])\n",
    "            f = [0] * (k + 1)\n",
    "            for i in range(1 , k + 1):\n",
    "                for j in range(0 , k):\n",
    "                    if i + j > k:\n",
    "                        continue\n",
    "                    f[i + j] = max(f[i + j] , dp[num][i] + dp[num * 2][j])\n",
    "            for i in range(1 , k + 1):\n",
    "                dp[num][i] = f[i]\n",
    "        if u.right != None:\n",
    "            self.dfs(u.right , num * 2 + 1, k , dp)\n",
    "            dp[num][0] += max(dp[num * 2 + 1])\n",
    "            f = [0] * (k + 1)\n",
    "            for i in range(1 , k + 1):\n",
    "                for j in range(0 , k):\n",
    "                    if i + j > k:\n",
    "                        continue\n",
    "                    f[i + j] = max(f[i + j] , dp[num][i] + dp[num * 2 + 1][j])\n",
    "            for i in range(1 , k + 1):\n",
    "                dp[num][i] = f[i]\n",
    "        \n",
    "        \n",
    "        return \n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        dp = {}\n",
    "        bk = {}\n",
    "        self.dfs(root , 1 , k , dp)\n",
    "        #print (dp[1])\n",
    "        return max(dp[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        def fun(node: TreeNode) -> List:\n",
    "            ret = [0 for _ in range(k + 1)]\n",
    "            if node == None:\n",
    "                return ret\n",
    "\n",
    "            arr = [-inf for _ in range(k + 1)]\n",
    "            le = fun(node.left)\n",
    "            ri = fun(node.right)\n",
    "            for i in range(k + 1):\n",
    "                for j in range(k + 1):\n",
    "                    if i + j <= k:\n",
    "                        arr[i + j] = max(arr[i + j], le[i] + ri[j])\n",
    "            \n",
    "            ret[0] = max(le) + max(ri)\n",
    "            for i in range(1, k + 1):\n",
    "                ret[i] = arr[i - 1] + node.val\n",
    "            return ret\n",
    "\n",
    "        return max(fun(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.record = self.k = None\n",
    "\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        self.record, self.k = {}, k\n",
    "        return self.fn(root, k)\n",
    "\n",
    "    def fn(self, root, k):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        if (root, k) in self.record:\n",
    "            return self.record[(root, k)]\n",
    "        max_v = self.fn(root.left, self.k) + self.fn(root.right, self.k)\n",
    "        if k > 0:\n",
    "            if (root, k-1) in self.record:\n",
    "                max_v = max(max_v, self.record[(root, k-1)])\n",
    "            else:\n",
    "                max_v = max(max_v, self.fn(root, k-1))\n",
    "        for ii in range(k):\n",
    "            max_v = max(max_v, root.val + self.fn(root.left, ii) + self.fn(root.right, k-ii-1))\n",
    "        self.record[(root, k)] = max_v\n",
    "        return max_v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        \n",
    "\n",
    "        def k2value(node):\n",
    "            value = {i:0 for i in range(k+1)}\n",
    "            if node:\n",
    "                left_blue = k2value(node.left)\n",
    "                right_blue = k2value(node.right)\n",
    "\n",
    "                for ln, lv in left_blue.items():\n",
    "                    for rn, rv in right_blue.items():\n",
    "                        value[0] = max(value[0], lv+rv)\n",
    "                        if ln + rn + 1 <= k:\n",
    "                            value[ln + rn + 1] = max(value[ln + rn + 1], lv + rv + node.val)\n",
    "            return value\n",
    "        \n",
    "        values = k2value(root)\n",
    "        return max(list(values.values()))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(root: Optional[TreeNode]):\n",
    "            res = [0]*(k+1)\n",
    "\n",
    "            if not root:\n",
    "                return res\n",
    "\n",
    "            l_vals = dfs(root.left)\n",
    "            r_vals = dfs(root.right)\n",
    "\n",
    "            res[0] = max(l_vals)+max(r_vals)\n",
    "            for i in range(1, k+1):\n",
    "                for l in range(0, i):\n",
    "                    res[i] = max(res[i], l_vals[l]+r_vals[i-l-1]) \n",
    "                res[i] += root.val\n",
    " \n",
    "            return res\n",
    "\n",
    "        return max(dfs(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # Definition for a binary tree node.\n",
    "# # class TreeNode:\n",
    "# #     def __init__(self, x):\n",
    "# #         self.val = x\n",
    "# #         self.left = None\n",
    "# #         self.right = None\n",
    "\n",
    "# class Solution:\n",
    "#     def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "#         @cache\n",
    "#         def fn(root, t):\n",
    "#             if not root:\n",
    "#                 return 0\n",
    "#             # 不染色\n",
    "#             res = fn(root.left, k) + fn(root.right, k)\n",
    "#             # 染色\n",
    "#             for l in range(t):\n",
    "#                 res = max(res, fn(root.left, l) + root.val + fn(root.right, t - l - 1))\n",
    "#             return res\n",
    "\n",
    "#         return fn(root, k)\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        @cache\n",
    "        def dfs(node):\n",
    "            # dp[i]表示当前node相连的有i个染色节点\n",
    "            # dp[0]表示当前node不染色\n",
    "            # dp[1]表示当前node染色，左右节点不染色\n",
    "            # dp[2]表示当前node染色了，左右节点其一染色(且染色节点的儿子节点未染色)\n",
    "            # ……\n",
    "            dp = [0] * (k + 1)\n",
    "            if not node:\n",
    "                return dp\n",
    "\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            dp[0] = max(left) + max(right)\n",
    "            for i in range(1, k+1):\n",
    "                dp[i] = max([left[l] +  right[i - l - 1] for l in range(i)]) + node.val\n",
    "            return dp\n",
    "        \n",
    "        return max(dfs(root))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(node) -> list[int]:\n",
    "            dp = [0] * (k + 1)\n",
    "            if not node:\n",
    "                return dp\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            \n",
    "            # 不涂色\n",
    "            dp[0] = max(left) + max(right)\n",
    "            #涂色\n",
    "            for i in range(1, k + 1):\n",
    "                dp[i] = max(left[l] + right[i - 1 - l] for l in range(i)) + node.val\n",
    "            \n",
    "            return dp\n",
    "        \n",
    "        return max(dfs(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        dp = defaultdict(lambda: [0] * (k+1))\n",
    "        def p(node):\n",
    "            if not node:\n",
    "                return\n",
    "            dp[node][1] = node.val\n",
    "            p(node.left)\n",
    "            p(node.right)\n",
    "            dp[node][0] = max(dp[node.left]) + max(dp[node.right])\n",
    "            for i in range(k, 0, -1):\n",
    "                for j in range(i-1, -1, -1):\n",
    "                    dp[node][i] = max(dp[node][i], node.val + dp[node.left][j] + dp[node.right][i-j-1])\n",
    "        p(root)\n",
    "        return max(dp[root])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        dp = collections.defaultdict(list)\n",
    "        dp[None] = [0] * (k+1)\n",
    "        def helper(node):\n",
    "            if node in dp:\n",
    "                return dp[node]\n",
    "            dp[node] = [0] * (k+1)\n",
    "            left = helper(node.left)\n",
    "            right = helper(node.right)\n",
    "            dp[node][0] = max(left) + max(right)\n",
    "            for i in range(1, k+1):\n",
    "                for j in range(i):\n",
    "                    dp[node][i] = max(dp[node][i], node.val + left[j] + right[i-1-j])\n",
    "            return dp[node]\n",
    "        return max(helper(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        dct = {}\n",
    "        self.idx = 0\n",
    "\n",
    "        def dfs(node, idx):\n",
    "            if idx not in dct: dct[idx] = [0] * (k + 1)\n",
    "            if not node: return\n",
    "\n",
    "            self.idx += 1\n",
    "            idxl = self.idx\n",
    "            self.idx += 1\n",
    "            idxr = self.idx\n",
    "\n",
    "            dfs(node.left, idxl)\n",
    "            dfs(node.right, idxr)\n",
    "\n",
    "            dct[idx][0] = max(dct[idxl][0], dct[idxl][-1]) + max(dct[idxr][0], dct[idxr][-1])\n",
    "\n",
    "            for ks in range(k + 1):\n",
    "                for i in range(ks):\n",
    "                    dct[idx][ks] = max(dct[idx][ks], dct[idxl][i] + max(dct[idxr][0], dct[idxr][ks - i - 1]) + node.val)\n",
    "\n",
    "\n",
    "        dfs(root, self.idx)\n",
    "        return max(dct[0][0], dct[0][-1])\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def myFunc(self, root, k):\n",
    "        if not root:\n",
    "            return 0\n",
    "        if self.memo.get((root, k)):\n",
    "            return self.memo[(root, k)]\n",
    "        res = self.myFunc(root.left, self.m) + self.myFunc(root.right, self.m)\n",
    "        if k > 0:\n",
    "            for i in range(k):\n",
    "                tmp = root.val + self.myFunc(root.left, i) + self.myFunc(root.right, k-1-i)\n",
    "                res = max(res, tmp)\n",
    "        self.memo[(root, k)] = res\n",
    "        return res\n",
    "\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        self.m = k\n",
    "        self.memo = {}\n",
    "        return self.myFunc(root, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        K = k\n",
    "        def dp(node, k):\n",
    "            if not node:\n",
    "                return 0\n",
    "            elif node in mem and mem[node][k] > 0:\n",
    "                return mem[node][k]\n",
    "            else:\n",
    "                if node not in mem:\n",
    "                    mem[node] = [0] * 11\n",
    "                res = dp(node.left, K) + dp(node.right, K)\n",
    "                for i in range(k):\n",
    "                    res = max(node.val + dp(node.left, i) + dp(node.right, k-i-1), res)\n",
    "                mem[node][k] = res\n",
    "                return mem[node][k]\n",
    "\n",
    "        # f[n][k] = max(v.val + {f[n.left][k-1] + f[n.right][k-1]}, f[n] )\n",
    "        mem = {}\n",
    "        return dp(root, k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        mem = {}\n",
    "        def dp(node, cnt):\n",
    "\n",
    "            if not node:\n",
    "                return 0\n",
    "            if (node, cnt) in mem:\n",
    "                return mem[node, cnt]\n",
    "            \n",
    "            res = 0\n",
    "            if cnt == 0: # node is not colored\n",
    "                for i in range(k+1):\n",
    "                    for j in range(k+1):\n",
    "                        res = max(res, dp(node.left, i) + dp(node.right, j))\n",
    "                        \n",
    "            else: # node is colored\n",
    "                for i in range(cnt):\n",
    "                    j = cnt - i - 1\n",
    "                    res = max(res, dp(node.left, i) + dp(node.right, j) + node.val)\n",
    "                \n",
    "            mem[node, cnt] = res\n",
    "            return res\n",
    "        \n",
    "        ans = max(dp(root, cnt) for cnt in range(k+1))\n",
    "        #print(mem)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        @cache\n",
    "        def f(x): #以x为根节点，蓝色n个\n",
    "            if x is None:return [0]*(k+1)\n",
    "            res=[0]*(k+1)\n",
    "            #如果不染\n",
    "       \n",
    "            left=f(x.left)\n",
    "            right=f(x.right)\n",
    "            t1=max(left)+max(right)\n",
    "            res[0]=t1\n",
    "\n",
    "            for i in range(1,k+1): #染的总个数\n",
    "                t2=0\n",
    "                for j in range(i):#左边的个数\n",
    "                    t2=max(t2,left[j]+right[i-j-1]+x.val)\n",
    "                res[i]=t2\n",
    "            return res\n",
    "        return max(f(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        @cache\n",
    "        def fn(root, t):\n",
    "            if not root:\n",
    "                return 0\n",
    "            # 不染色\n",
    "            res = fn(root.left, k) + fn(root.right, k)\n",
    "            # 染色\n",
    "            for l in range(t):\n",
    "                res = max(res, fn(root.left, l) + root.val + fn(root.right, t - l - 1))\n",
    "            return res\n",
    "\n",
    "        return fn(root, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        @cache\n",
    "        def f(r, k1):\n",
    "            if not r:\n",
    "                return 0\n",
    "            w = f(r.left, k) + f(r.right, k)\n",
    "            if k1 == 0:\n",
    "                return w\n",
    "            k2 = k1 - 1\n",
    "            return max(w, max(f(r.left, i) + f(r.right, k2 - i) for i in range(k1)) + r.val)\n",
    "\n",
    "        return f(root, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        @cache\n",
    "        def f(o, k0):\n",
    "            if not o:\n",
    "                return 0\n",
    "\n",
    "            rnt = f(o.left, k) + f(o.right, k)\n",
    "\n",
    "            if k0 == 0:\n",
    "                return rnt\n",
    "            # if k0 == 1:\n",
    "            #     return max(rnt, o.val)\n",
    "            \n",
    "\n",
    "            for i in range(k0):\n",
    "                rnt = max(rnt, o.val + f(o.left, i) + f(o.right, k0-1-i))\n",
    "            return rnt\n",
    "\n",
    "        return f(root, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        @cache\n",
    "        def dp(node,canLink):\n",
    "            if not node:\n",
    "                return 0\n",
    "            notLink = dp(node.left,k)+dp(node.right,k)\n",
    "            if canLink:\n",
    "                link = node.val+max(dp(node.left,i)+dp(node.right,canLink-1-i) for i in range(canLink))\n",
    "            else:\n",
    "                link = 0\n",
    "            return max(notLink,link)\n",
    "        return dp(root,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        record = {}\n",
    "        @lru_cache(None)\n",
    "        def dfs(root,count):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            total =  0\n",
    "            for i in range(count):\n",
    "                total = max(total,root.val+dfs(root.left,i)+dfs(root.right,count-i-1))\n",
    "            total = max(total,dfs(root.left,k)+dfs(root.right,k))\n",
    "            return total\n",
    "        return dfs(root,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        @cache\n",
    "        def dfs(root,a):\n",
    "            if not root:\n",
    "                return 0\n",
    "            if a == 0:\n",
    "                return dfs(root.left,k) + dfs(root.right,k)\n",
    "\n",
    "            ans1 = dfs(root.left,k) +  dfs(root.right,k)\n",
    "\n",
    "            # ans2 = root.val\n",
    "            for i in range(0,a):\n",
    "                ans1 = max(root.val + dfs(root.left,i) + dfs(root.right,a-i-1),ans1)\n",
    "\n",
    "            return ans1\n",
    "        return dfs(root,k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        @cache\n",
    "        def dfs(node: TreeNode, m: int) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            # not select cur\n",
    "            ans1 = dfs(node.right, k) + dfs(node.left, k)\n",
    "            ans2 = 0\n",
    "            # select cur\n",
    "            if m > 0:\n",
    "                ans2 = node.val\n",
    "                for t in range(m):  # 0~m-1a\n",
    "                    ans2 = max(ans2, dfs(node.left, t) + dfs(node.right, m - 1 - t) + node.val)\n",
    "            return max(ans1, ans2)\n",
    "        return dfs(root, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        @cache\n",
    "        def dfs(root,cnt):\n",
    "            if not root:\n",
    "                return 0\n",
    "            if cnt==0:\n",
    "                return dfs(root.left,k)+dfs(root.right,k)\n",
    "            res1=dfs(root.left,k)+dfs(root.right,k) \n",
    "            res2=max([dfs(root.left,i)+dfs(root.right,cnt-1-i) for i in range(cnt)])+root.val\n",
    "            res=max(res1,res2)\n",
    "            return res\n",
    "        return dfs(root,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        @cache\n",
    "        def dfs(root: TreeNode, cnt: int):\n",
    "            if not root:return 0\n",
    "            if not cnt:\n",
    "                return dfs(root.left, k) + dfs(root.right, k)\n",
    "            \n",
    "            # 不染色\n",
    "            ans = dfs(root.left, k) + dfs(root.right, k)\n",
    "\n",
    "            # 染一颗子树\n",
    "            # ans = max(ans, dfs(root.left, cnt - 1) + dfs(root.right, k))\n",
    "            # ans = max(ans, dfs(root.left, k) + dfs(root.right, cnt - 1))\n",
    "\n",
    "            # 染两颗子树\n",
    "            for l in range(cnt):\n",
    "                ans = max(ans, root.val + dfs(root.left, l) + dfs(root.right, cnt - 1 - l))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(root, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        # 每个节点都有染或不染两种选择，因此可能可以用树上DP\n",
    "        @ cache\n",
    "        def dfs(node:TreeNode,i:int): # i表示以node为树根，有多少个相邻点染色\n",
    "            if node is None:\n",
    "                return 0\n",
    "            if i==0:\n",
    "                temp=-math.inf\n",
    "                for m in range(k+1):\n",
    "                    for n in range(k+1):\n",
    "                        temp=max(temp,dfs(node.left,m)+dfs(node.right,n))\n",
    "                return temp\n",
    "            elif i==1:\n",
    "                return dfs(node.left,0)+dfs(node.right,0)+node.val\n",
    "            else:\n",
    "                temp=-math.inf\n",
    "                for m in range(i):\n",
    "                    temp=max(temp,dfs(node.left,m)+dfs(node.right,i-1-m))\n",
    "                return temp+node.val\n",
    "        ans=-math.inf\n",
    "        for i in range(k+1):\n",
    "            ans=max(ans,dfs(root,i))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "    \n",
    "        @cache\n",
    "        def func(root, n):\n",
    "\n",
    "            if not root:\n",
    "                return 0\n",
    "\n",
    "            \n",
    "\n",
    "            left = func(root.left, k)\n",
    "            right = func(root.right, k)\n",
    "            if n == 0:\n",
    "                return left + right\n",
    "\n",
    "            mid = max(root.val + func(root.left, i) + func(root.right, n-1-i) for i in range(0, n))\n",
    "            \n",
    "            mx = max(left + right, mid)\n",
    "            print(root.val, n , mx)\n",
    "            return mx \n",
    "        \n",
    "        return func(root, k)\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        def dfs(root, k):\n",
    "            global K\n",
    "            if not root:\n",
    "                return 0\n",
    "            if (root, k) in dic:\n",
    "                return dic[(root, k)]\n",
    "\n",
    "            l, r = dfs(root.left, self.k), dfs(root.right, self.k)\n",
    "            res = l + r\n",
    "            for i in range(k):\n",
    "                res = max(res, root.val + dfs(root.left, i) + dfs(root.right, k - i - 1))\n",
    "            \n",
    "            dic[(root, k)] = res\n",
    "            return res\n",
    "        \n",
    "        dic = {}\n",
    "        self.k = k\n",
    "        return dfs(root, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        def myFunc(root,x):\n",
    "            if m.__contains__(str(id(root))+str(x)):\n",
    "                return m[str(id(root))+str(x)]\n",
    "            maxvalue = 0\n",
    "            if not root:\n",
    "                return 0\n",
    "            if x == 0:\n",
    "                return myFunc(root.left,k) + myFunc(root.right,k)\n",
    "            for i in range(x):\n",
    "                a = m.get(str(id(root.left))+str(x-1-i)) if m.__contains__(str(id(root.left))+str(x-1-i)) else myFunc(root.left,x-1-i)\n",
    "                b = m.get(str(id(root.right))+str(i)) if m.__contains__(str(id(root.right))+str(i)) else myFunc(root.right,i)\n",
    "                    \n",
    "                maxvalue = max(root.val+a+b,maxvalue)\n",
    "            c = m.get(str(id(root.left))+str(k)) if m.__contains__(str(id(root.left))+str(k)) else myFunc(root.left,k)\n",
    "            d = m.get(str(id(root.right))+str(k)) if m.__contains__(str(id(root.right))+str(k)) else myFunc(root.right,k)\n",
    "            maxvalue = max(c+d,maxvalue)\n",
    "            m[str(id(root))+str(x)] = maxvalue\n",
    "            return maxvalue\n",
    "        \n",
    "        m = {}\n",
    "        return myFunc(root,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.d = {}\n",
    "\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        ret = float('-inf')\n",
    "        for c in range(k+1):\n",
    "            tmp = self.func(root,k,c)\n",
    "            ret = max(ret,tmp)\n",
    "        return ret\n",
    "\n",
    "    def func(self,root,k,c): #返回一个节点作为根节点,且和根节点连接的蓝色区域有c个,的最大值\n",
    "        if root==None:\n",
    "            return 0\n",
    "\n",
    "        rr = self.d.get((id(root),c))\n",
    "        if rr!=None:\n",
    "            return rr\n",
    "\n",
    "        ret = None\n",
    "        if c==0:\n",
    "            #root不能选,则左右各取最大\n",
    "            ret = 0\n",
    "            extra = 0\n",
    "            #左右加起来最多有c-1个\n",
    "            for left_i in range(k+1): #左边有left_i个:\n",
    "                if root.left==None:\n",
    "                    left_i = 0\n",
    "                for right_i in range(k+1): #右边有right_i个\n",
    "                    if root.right==None:\n",
    "                        right_i = 0\n",
    "                    ret_l = self.func(root.left,k,left_i)\n",
    "                    ret_r = self.func(root.right,k,right_i)\n",
    "                    extra = max(ret_l+ret_r,extra)\n",
    "                    if root.right==None:\n",
    "                        break\n",
    "                if root.left==None:\n",
    "                    break\n",
    "            ret += extra\n",
    "        elif c==1:\n",
    "            #只要root\n",
    "            ret = root.val + self.func(root.left,k,0) + self.func(root.right,k,0)\n",
    "        else:\n",
    "            ret = root.val #选root\n",
    "            extra = 0\n",
    "            #左右加起来最多有c-1个\n",
    "            for left_i in range(c): #左边有left_i个:\n",
    "                if root.left==None:\n",
    "                    left_i = 0\n",
    "                for right_i in range(c-left_i): #右边有right_i个\n",
    "                    if root.right==None:\n",
    "                        right_i = 0\n",
    "                    ret_l = self.func(root.left,k,left_i)\n",
    "                    ret_r = self.func(root.right,k,right_i)\n",
    "                    extra = max(ret_l+ret_r,extra)\n",
    "                    if root.right==None:\n",
    "                        break\n",
    "                if root.left==None:\n",
    "                    break\n",
    "            ret += extra\n",
    "\n",
    "\n",
    "        self.d[(id(root),c)] = ret\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        mp = {}\n",
    "        # @lru_cache(None)\n",
    "        def traversal(root, k):\n",
    "            if (root, k) in mp:\n",
    "                return mp[(root, k)]\n",
    "\n",
    "            if not root:\n",
    "                if k == 0:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return float('-inf')\n",
    "\n",
    "            if k >= 1:    \n",
    "                ans = 0\n",
    "                # color\n",
    "                tmp = root.val\n",
    "                for i in range(k):\n",
    "                    left = i\n",
    "                    right = k - 1 - i \n",
    "                    ll = traversal(root.left, left)\n",
    "                    rr = traversal(root.right, right)\n",
    "\n",
    "                    ans = max(ans, tmp + ll + rr)\n",
    "            else:\n",
    "                ans = 0\n",
    "                for i in range(self.k + 1):\n",
    "                    for j in range(self.k + 1):\n",
    "                        left = i \n",
    "                        right = j\n",
    "                        ll = traversal(root.left, left)\n",
    "                        rr = traversal(root.right, right)\n",
    "                        \n",
    "                        ans = max(ans, ll + rr)\n",
    "\n",
    "\n",
    "            mp[(root, k)] = ans\n",
    "                \n",
    "            return ans\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "        self.k = k\n",
    "\n",
    "        for i in range(k + 1):\n",
    "            ans = max(ans, traversal(root, i))\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        cache = {}\n",
    "\n",
    "        def inner_helper(node: TreeNode, length: int):\n",
    "            nonlocal cache\n",
    "            if node is None: return 0\n",
    "            cache_key = (node, length)\n",
    "            data = cache.get(cache_key)\n",
    "            if data is not None: return data\n",
    "\n",
    "            left, right = node.left, node.right\n",
    "            left_val = inner_helper(left, k)\n",
    "            right_val = inner_helper(right, k)\n",
    "            max_val = left_val + right_val\n",
    "            if length == 0:\n",
    "                cache[cache_key] = max_val\n",
    "                return max_val\n",
    "\n",
    "            leftover = length - 1\n",
    "            cur_val = node.val\n",
    "            max_val -= cur_val\n",
    "            # include cur_node\n",
    "            for i in range(length):\n",
    "                max_val = max(\n",
    "                    max_val,\n",
    "                    inner_helper(left, i) + inner_helper(right, leftover - i)\n",
    "                )\n",
    "            res = max_val + cur_val\n",
    "            cache[cache_key] = res\n",
    "            return res\n",
    "        return inner_helper(root, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    \n",
    "    def __init__(self):\n",
    "        self.k = None\n",
    "        self.child_cnt = {}\n",
    "        self.ans = {}\n",
    "        \n",
    "    @functools.lru_cache\n",
    "    def get_child_cnt(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.child_cnt[root] = 1 + self.get_child_cnt(root.left) + self.get_child_cnt(root.right)\n",
    "        return self.child_cnt[root]\n",
    "\n",
    "\n",
    "    @functools.lru_cache\n",
    "    def helper(self, root, k):\n",
    "        if not root or k < 0:\n",
    "            return 0\n",
    "\n",
    "        if not root.left and not root.right:\n",
    "            if k > 0:\n",
    "                return root.val\n",
    "            if k == 0:\n",
    "                return 0\n",
    "        \n",
    "        if (root, k) not in self.ans:\n",
    "            # root不染色，左右子节点重新计算k\n",
    "            if k == 0:\n",
    "                ans = self.helper(root.left, self.k) + self.helper(root.right, self.k)\n",
    "                \n",
    "\n",
    "            else:\n",
    "                # 不染root，左右子节点重新计算k\n",
    "                mark_no_root = self.helper(root.left, self.k)+ self.helper(root.right, self.k)\n",
    "\n",
    "                # 染root，左右子节点划分k-1\n",
    "                mark_root = 0\n",
    "                if root.left:\n",
    "                    idx = min(k-1, self.child_cnt[root.left])\n",
    "                    for i in range(idx+1):\n",
    "                        mark_root = max(\n",
    "                            mark_root,\n",
    "                            self.helper(root.left, i) + self.helper(root.right, k - 1 - i))\n",
    "                else:\n",
    "                    mark_root = self.helper(root.right, k-1)\n",
    "                mark_root += root.val\n",
    "\n",
    "                ans = max(mark_no_root, mark_root)\n",
    "            \n",
    "            self.ans[(root, k)] = ans\n",
    "            return ans\n",
    "        else:\n",
    "            return self.ans[(root, k)]\n",
    "\n",
    "\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        self.k = k\n",
    "        self.get_child_cnt(root)\n",
    "        return self.helper(root, k)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        dp = defaultdict(lambda : defaultdict(int))\n",
    "\n",
    "        def dfs(node: TreeNode):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            maxleft = dfs(node.left)\n",
    "            maxright = dfs(node.right)\n",
    "            dp[node][0] = maxleft + maxright\n",
    "            for i in range(k):\n",
    "                for j in range(k-i):\n",
    "                    dp[node][i+j+1] = max(dp[node][i+j+1], dp[node.left][i] + dp[node.right][j] + node.val)\n",
    "            ret = 0\n",
    "            for i in range(k+1):\n",
    "                ret = max(ret, dp[node][i])\n",
    "            return ret\n",
    "\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def inner_helper(node: TreeNode, length: int):\n",
    "            left, right = node.left, node.right\n",
    "            if left is not None and right is not None:\n",
    "                left_val = inner_helper(left, k)\n",
    "                right_val = inner_helper(right, k)\n",
    "                max_val = left_val + right_val\n",
    "                if length == 0: return max_val\n",
    "                leftover = length - 1\n",
    "                cur_val = node.val\n",
    "                max_val -= cur_val\n",
    "                for i in range(length):\n",
    "                    max_val = max(\n",
    "                        max_val,\n",
    "                        inner_helper(left, i) + inner_helper(right, leftover - i)\n",
    "                    )\n",
    "                max_val += cur_val\n",
    "            elif left is not None:\n",
    "                max_val = inner_helper(left, k)\n",
    "                if length == 0: return max_val\n",
    "                max_val = max(max_val,\n",
    "                            node.val + inner_helper(left, length - 1))\n",
    "            elif right is not None:\n",
    "                max_val = inner_helper(right, k)\n",
    "                if length == 0: return max_val\n",
    "                max_val = max(max_val,\n",
    "                            node.val + inner_helper(right, length - 1))\n",
    "            elif length == 0: return 0\n",
    "            else: max_val = node.val\n",
    "            return max_val\n",
    "        return inner_helper(root, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxValue(self, root: TreeNode, k: int) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def traversal(root, k):\n",
    "            if not root:\n",
    "                if k == 0:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return float('-inf')\n",
    "\n",
    "            if k >= 1:    \n",
    "                ans = 0\n",
    "                # color\n",
    "                tmp = root.val\n",
    "                for i in range(k):\n",
    "                    left = i\n",
    "                    right = k - 1 - i \n",
    "                    ll = traversal(root.left, left)\n",
    "                    rr = traversal(root.right, right)\n",
    "\n",
    "                    ans = max(ans, tmp + ll + rr)\n",
    "            else:\n",
    "                ans = 0\n",
    "                for i in range(self.k + 1):\n",
    "                    for j in range(self.k + 1):\n",
    "                        left = i \n",
    "                        right = j\n",
    "                        ll = traversal(root.left, left)\n",
    "                        rr = traversal(root.right, right)\n",
    "                        \n",
    "                        ans = max(ans, ll + rr)\n",
    "\n",
    "                \n",
    "            return ans\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "        self.k = k\n",
    "\n",
    "        for i in range(k + 1):\n",
    "            ans = max(ans, traversal(root, i))\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
